#include <bits/stdc++.h>
using namespace std;

class Solution
{
  public:
    vector<vector<int>> permuteUnique(vector<int> &num)
    {
        sort(num.begin(), num.end()); // 排序使相同元素相邻
        st.resize(num.size(), false); // 初始化记忆数组
        backtrack(num, 0);            // 调用回溯函数
        return res;                   // 返回结果
    }

  private:
    vector<vector<int>> res; // 存储所有排列结果
    vector<bool> st;         // 记忆数组，标记元素是否使用过
    vector<int> path;        // 当前组合

    void backtrack(vector<int> &num, int start)
    {
        if (start == num.size())
        {                        // 终止条件：当前路径长度等于数组长度
            res.push_back(path); // 将当前路径加入结果集
            return;
        }
        for (int i = 0; i < num.size(); ++i)
        {
            if (st[i])
                continue; // 跳过已使用的元素
            // 剪枝条件：当前元素与前一个相同，且前一个未被使用时跳过
            if (i > 0 && num[i] == num[i - 1] && !st[i - 1])
                continue;

            st[i] = true;              // 标记当前元素为已使用
            path.push_back(num[i]);    // 将当前元素加入路径
            backtrack(num, start + 1); // 递归进入下一层
            path.pop_back();           // 回溯：移除当前元素
            st[i] = false;             // 回溯：标记当前元素为未使用
        }
    }
};

class Solution
{
  private:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> res;
    void backTrack(vector<int> &num, int start)
    {
        if (start == num.size())
        {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < num.size(); i++)
        {
            if (i > 0 && num[i] == num[i - 1] && !st[i - 1])
                continue;
            if (!st[i])
            {
                st[i] = true;
                path[start] = num[i];
                backTrack(num, start + 1);
                path.pop_back();
                st[i] = false;
            }
        }
    }

  public:
    vector<vector<int>> permuteUnique(vector<int> &num)
    {
        sort(num.begin(), num.end()); // 排列数组元素，方便跳过重复
        st.resize(num.size() , false);
        path.resize(num.size() + 1);
        backTrack(num, 0);
        return res;
    }
};